﻿/*
	题目：
	将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例：

输入：1->2->4->6, 1->3->4->5
输出：1->1->2->3->4->4
思路:1、一个个遍历
2、递归

*/
#include <iostream>
#include "LinkList.h"


class Solution
{
public:
	Solution();
	~Solution() {};
	void Init();
	//逻辑：把逐渐拼接后的链表接在前面,递归就是把一个个数接在后面
	LinkNode* MergeTwoList(LinkNode* head1, LinkNode* head2) {
		//如果head1 和 head2有一个为空 则直接返回另一个
		if (!head1) {
			return head2;
		}
		if (!head2) {
			return head1;
		}
		if (head1->szData < head2->szData) {
			head1->next = MergeTwoList(head1->next, head2);
			return head1;
		}
		else {
			head2->next = MergeTwoList(head1, head2->next);
			return head2;
		}
	}

private:
	
};

Solution::Solution()
{

}

void Solution::Init()
{

}


int main()
{
	LinkList linklist;
	LinkList linklist2;
	linklist.InitList(1);
	linklist.AddNode(2);
	linklist.AddNode(4);
	linklist.AddNode(6);
	linklist2.InitList(1);
	linklist2.AddNode(3);
	linklist2.AddNode(4);
	linklist2.AddNode(5);

	Solution solution;
	solution.Init();
	LinkNode * HeadNode = solution.MergeTwoList(linklist.GetFirst(), linklist2.GetFirst());
	if (HeadNode == nullptr)
		return 0;
	
	int count = 0;
	LinkNode * node = HeadNode;
	while (node != nullptr) {
		std::cout << "[" << count++ << "] is :" << node->szData << std::endl;
		node = node->next;
	};
	std::cout << "linklist 1" << std::endl;
	linklist.Display();
	std::cout << "linklist 2" << std::endl;
	linklist2.Display();
}
